package 测试;

import java.util.*;

public class Test3 {

    //这个是按字典输出的
    void all(int a[], List<Integer> r, Set<Integer> set, List<List<Integer>> alist){
        int now = set.size();
        if(now==a.length){
            List<Integer> t = new ArrayList<>(r);
            alist.add(t);
            return;
        }
        for (int t : a) {
            if(!set.contains(t)){
                r.add(t);
                set.add(t);
                all(a,r,set,alist);
                r.remove(now);
                set.remove(t);
            }
        }
    }
    //将数组分为两个部分，将已选择的元素通过交换放在左侧，这样在查询元素是否包含时性能更好，但是输出时不是字典顺序的
    void backtrack(List<Integer> t, List<List<Integer>> alist,int now){ //now: 前面now个已选择
        if(now==t.size())
            alist.add(new ArrayList<>(t));
        for (int i = now; i <t.size(); i++) {
            //将已选择的交换到下标为now处
            int x = t.get(i);
            t.set(i,t.get(now));
            t.set(now,x);
            backtrack(t,alist,now+1);
            //恢复现场
            x = t.get(i);
            t.set(i,t.get(now));
            t.set(now,x);
            
        }
    }
    public List<List<Integer>> permute(int[] nums) {
        List<Integer> r = new ArrayList<>(nums.length);
        Set<Integer> set = new HashSet<>();
        List<List<Integer>> alist = new ArrayList<>();
        all(nums,r,set,alist);
        return alist;
    }

    public static void main(String[] args) {
        int[] a = new int[]{1,2,3,4,5};
        Test3 test3 = new Test3();
        List<List<Integer>> permute = test3.permute(a);
        System.out.println(permute);
    }
}
